package cg.studio.practise;

import org.junit.Test;

import cg.studio.algorithm.sort.SortUtil;
import cg.studio.model.Pair;

public class Arrays
{
  //@Test
  public void testFindLargestNumbers()
  {
    {
      int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8 };
      findLargestNumbers( numbers, 5 );
      printArray( numbers );
      System.out.println();
    }

    {
      int[] numbers = { 9,8,7,6,5,4,3,2,1 };
      findLargestNumbers( numbers, 5 );
      printArray( numbers );
      System.out.println();
    }

  }
  
  //@Test
  public void testFindClosestZeroPair()
  {
    testFindClosestZeroPair( new int[]{ 1, 2, -3, 4, -5, -6, 7, 8 } );
    testFindClosestZeroPair( new int[]{ 5, 6, 7, 8 } );
    testFindClosestZeroPair( new int[]{ -5, 6, 9, -9, 7 } );
  }
  
  public void testFindClosestZeroPair( int[] numbers )
  {
    
    Pair<?,?> pair = findClosestZeroPair( numbers );
    printArray( numbers );
    System.out.print( ": " );
    System.out.println( pair );
  }
  
  @Test
  public void testGetMinCost_1()
  {
    testGetMinCost_1( new int[]{ 1, 2, 3 }, 4 );
    testGetMinCost_1( new int[]{ 5, 6, 7 }, 8 );
    testGetMinCost_1( new int[]{ 1, 2, 3 }, 8 );
  }
  
  public void testGetMinCost_1( int[] marks, int len )
  {
    System.out.println( getMinCost_1( marks, len ) );
  }
  
  //////////////////////////////////////////////////////////////////////////////////////////////////////////////
  
  /**
   * Find the second most repeating number in an array without using extra storage.
   * - one solution is using HashMap( number==>count), but still need to go through the count to find correct number
   *   complex: O(n) if Hash function good enough
   * - sort: quick sort(nlgn), and then go through to find second most repeating number
   */
  
  
  /**
   * find the largest m numbers from input <numbers>
   * or put the largest m number in the left side array, namely the left m number of array are the largest m number.
   * 
   * 1. of course we can sort all numbers and then get the largest m number.
   * 2. select the largest number from array, move to left and then go on. complexity: m*n 
   * 3. we can select left m number as selected numbers, and for left numbers, just compare with the smallest select number,
   *    if the number large than smallest number, replaced it and find the smallest number and go on. 
   *    complexity: m*(n-m), but better than solution 2 when m are very large, for exmaple m=n-1, complexity is n
   * 4. use same logic as quick sort. select a number divided into 2 sub-array, left side are large numbers; if the size
   *    of left sub-array( p ) equal m, then done; if larger than m, then can discard right sub-array; if smaller than m, 
   *    no need to sort left sub-array, can the problem converted to find m-p of right sub array
   *   
   * @param numbers
   * @param m
   * 
   */
  public static void findLargestNumbers( int[] numbers, int m )
  {
    if( m == 0 || numbers.length <= 1 )
      return;
    findLargestNumbers( numbers, 0, numbers.length-1, m );
  }
  
  protected static void findLargestNumbers( int[] numbers, final int left0, int right0, int m )
  {
    if( m == 0 || numbers.length <= 1 || left0 == right0 )
      return;
    int comparing = (numbers[left0] + numbers[right0])/2;
    int left = left0;
    int right = right0;
    while( left < right )
    {
      while( numbers[left] >= comparing && left < right )
        left++;
      while( numbers[right] < comparing && left < right )
        right--;
      if( left < right )
      {
        //switch
        int tmp = numbers[left];
        numbers[left] = numbers[right];
        numbers[right] = tmp;
      }
    }
    
    //left == right now
    if( left == m )
      return;
    if( left > m )
    {
      findLargestNumbers( numbers, 0, left, m );
      return;
    }
    
    findLargestNumbers( numbers, left, right0, m-left );
  }
  
  
  /**
   * Given an array of numbers, find a pair whose sum is closest to zero.
   * 
   * Solution: sort as then sum
   * @param values
   * @return
   */
  public static Pair< Integer, Integer > findClosestZeroPair( int[] values )
  {
    return findSumClosestTo( values, 0 );
  }
  
  /**
   * find a pair in the array, which sum are most close to the <expectedSum>
   * @param values
   * @param expectedSum
   * @return
   */
  public static Pair< Integer, Integer > findSumClosestTo( int[] values, final int expectedSum )
  {
    SortUtil.quickSort( values );
    Integer closedSum = null;
    
    Pair< Integer, Integer > pair = new Pair< Integer, Integer >();
    int left=0, right=values.length-1;
    while( right>left )
    {
      int sum = values[left]+values[right];
      if( sum == expectedSum )
      {
        pair.setValue1( values[left] );
        pair.setValue2( values[right] );
        break;
      }
      if( closedSum == null || Math.abs(closedSum-expectedSum) > Math.abs( sum-expectedSum ) )
      {
        closedSum = sum;
        pair.setValue1( values[left] );
        pair.setValue2( values[right] );
      }
      if( sum > 0 )
        --right;
      else
        ++left;
    }
    return pair;
  }
  
  
  /**
   * You are given a log of wood of length `n’. There are `m’ markings on the log. 
   * The log must be cut at each of the marking. The cost of cutting is equal to the length of the log that is being cut. 
   * Given such a log, determine the least cost of cutting.
   * 
   * Analysis: this problem can be converted to input an integer array with m size which represents the location 
   * of the log, and return the min cost
   * 
   * for example, n=4, marks={1,2,3}, which mean marks separate logs into 4 even section.
   * we can cut at second mark(2), the log becomes 2 logs, log1( length=2, marks={1} ), log2( length=2, marks={3} )
   * so, total cost is 4 + 2 + 2 = 8
   * 
   * Solution 1: if marks also represents the order of cut, then this problem convert to order this marks, 
   * calculate the cost and pick the min one. 
   * 
   * solution2: treat it as a binary tree, each tree node has information ( cost, mark-index, mark-value/left-length )
   * so, root( n, i, v[i] ), left( v[i], j, v[j] ), right( n-v[i], p, v[p]-v[i] );
   * so, for any depth, if it is full in this depth, the sum of cost in this depth is n
   * if both trees is full tree, only need to compare deepest node.
   * if the tree is not full tree, the cost of this tree should large than the full tree( how to prove? or may not )
   * 
   *  
   * @param arr
   */
  //use recursive to get the possible costs and get the min one
  public static int getMinCost_1( int[] marks, int len )
  {
    if( marks == null || marks.length==0 )
      return 0;
    if( marks.length == 1 )
      return len;
    return getMinCost_1( marks, 0, marks.length-1, len, 0 );
  }
  
  /**
   * 
   * @param marks
   * @param start
   * @param end
   * @param len the length of current log
   * @param subtractLen when the log cut, the marks of right log should be subtract the length of left log,
   *   use this parameter to represents this length to avoid subtraction
   * @return
   */
  public static int getMinCost_1( int[] marks, int start, int end, int len, int subtractLen )
  {
    if( end < start )
      return 0;
    if( start == end )
      return len;
    
    int minCost = Integer.MAX_VALUE;
    for( int i=start; i<=end; ++i )
    {
      int cost = len + getMinCost_1( marks, start, i-1, marks[i]-subtractLen, subtractLen ) 
               + getMinCost_1( marks, i+1, end, len-(marks[i]-subtractLen), marks[i]+subtractLen );
      if( cost < minCost )
        minCost = cost;
    }
    return minCost;
  }
  
  public static int getMinCost( int[] marks, int n )
  {
    return 0;
  }


  public static int cost( int[] marks, int n )
  {
    return cost( marks, marks.length, n );
  }
  /**
   * calculate the cut cost if we cut log with sequence indicated by marks
   * 
   * @param marks
   * @param size the actual size of the marks
   * @param n
   * @return
   */
  public static int cost( int[] marks, int size, int n )
  {
    if( size == 1 )
      return n;
    
    int cost = n;
    //cut at the first mark, and this cut the log into two logs
    int curMark = marks[0];
    int n1 = curMark;
    int n2 = n - n1;
    //all the marks which less than mark are in the left log, and larger marks are in the right log
    //as the order of marks is the order of cut, should not change their order.
    //can NOT use the swap logic
    marks[0] = 0;   //0 as the invalid mark
    int[] leftMarks = new int[ size-1 ];  //max size of left log is size-1
    int leftSize = 0;
    int rightSize = 0;
    for( int i=1; i<marks.length; ++i )
    {
      //all marks which larger and equal mark should in right log
      if( marks[i] >= curMark )
      {
        marks[rightSize++] = marks[i]-curMark;
      }
      else // all marks less than mark should in left log
      {
        leftMarks[leftSize++] = curMark;
      }
    }
    
    cost += cost( leftMarks, leftSize, n1 );
    cost += cost( marks, rightSize, n2 );
    
    return cost;
  }
  
  
  public static void printArray( int[] arr )
  {
    printArray( arr, arr.length );
  }
  
  public static void printArray( int[] arr, int length )
  {
    if( length > arr.length )
      throw new IllegalArgumentException( "The length should NOT larger than array length." );
    for ( int i = 0; i < length; i++ )
      System.out.print( arr[i] + ", " );
  }

}
